// https://leetcode.cn/problems/text-justification/?envType=study-plan-v2&envId=top-interview-150

// 算法思路总结：
// 1. 贪心算法确定每行可容纳的单词数量
// 2. 最后一行或单单词行左对齐，尾部填充空格
// 3. 其他行均匀分布空格，多余空格从左到右分配
// 4. 时间复杂度：O(N)，空间复杂度：O(N)

// 本题主函数由AI生成

#include <iostream>
using namespace std;

#include <vector>
#include <algorithm>
#include <string>

class Solution 
{
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) 
    {
        int n = words.size();
        
        vector<string> result;
        int i = 0;
        while (i < n) 
        {
            int j = i;
            int curLen = 0;
        
            while (j < n && curLen + words[j].length() + (j - i) <= maxWidth) 
            {
                curLen += words[j].length();
                j++;
            }
            
            string line;
            int wordCount = j - i;  
            int totalSpaces = maxWidth - curLen;  
            
            if (j == n || wordCount == 1) 
            {
                for (int k = i ; k < j ; k++)
                {
                    line += words[k];
                    if (k < j - 1) 
                    {
                        line += " ";
                        totalSpaces--;
                    }
                }
                line += string(totalSpaces, ' ');
            } 
            else 
            {
                int baseSpaces = totalSpaces / (wordCount - 1);  
                int extraSpaces = totalSpaces % (wordCount - 1); 
                
                for (int k = i; k < j; k++) 
                {
                    line += words[k];
                    
                    if (k < j - 1) 
                    {
                        line += string(baseSpaces, ' ');
                        
                        if (extraSpaces > 0) 
                        {
                            line += " ";
                            extraSpaces--;
                        }
                    }
                }
            }
            
            result.push_back(line);
            i = j; 
        }
        
        return result;
    }

    void printResult(vector<string>& result)
    {
        for (const string& line : result)
        {
            cout << "\"" << line << "\"" << endl;
        }
        cout << endl;
    }
};

int main() 
{
    Solution solution;
    
    // 测试用例1
    vector<string> words1 = {"This", "is", "an", "example", "of", "text", "justification."};
    auto result1 = solution.fullJustify(words1, 16);
    solution.printResult(result1);
    
    // 测试用例2：单词长度等于maxWidth
    vector<string> words2 = {"abcdefghijklmn"};
    auto result2 = solution.fullJustify(words2, 14);
    solution.printResult(result2);
    
    // 测试用例3：多个短单词
    vector<string> words3 = {"a", "b", "c", "d", "e"};
    auto result3 = solution.fullJustify(words3, 5);
    solution.printResult(result3);
    
    return 0;
}